// BigInt.cpp
#include "BigInt.h"
#include <string.h>

namespace Jidantou {
    BigInt::BigInt(int64_t num) {
        if (num < 0) {
            _sign = 1;
            for (int i = 1; i < LONGLONG_NUM; i++) {
                _number[i] = 0xFFFFFFFFFFFFFFFF;
            }
        }
        else {
            _sign = 0;
            for (int i = 1; i < LONGLONG_NUM; i++) {
                _number[i] = 0;
            }
        }
        _number[0] = num;
    }

    BigInt& BigInt::operator=(const BigInt& num2) {
        _sign = num2._sign;
        for (int i = 0; i < LONGLONG_NUM; i++) {
            _number[i] = num2._number[i];
        }

        return *this;
    }

    BigInt BigInt::operator-() const {
        BigInt num2(0);
        int i, carry = 1;

        num2._sign = _sign == 0 ? 1 : 0;

        for (i = 0; i < LONGLONG_NUM; i++) {
            num2._number[i] = ~_number[i] + carry;
            carry = _number[i] == 0 && carry == 1 ? 1 : 0;
        }

        return num2;
    }

    BigInt BigInt::operator+(const BigInt& num2) const {
        BigInt num3;
        int i, carry = 0, carry_next;
        uint64_t temp;

        for (i = 0; i < LONGLONG_NUM - 1; i++) {
            temp = _number[i] + num2._number[i];
            carry_next = (temp < _number[i] && temp < num2._number[i]) || (temp == 0xFFFFFFFFFFFFFFFF && carry == 1) ? 1 : 0;
            num3._number[i] = temp + carry;
            carry = carry_next;
        }
        temp = _number[i] + num2._number[i];
        num3._sign = (_sign ^ num2._sign) ^ ((temp < _number[i] && temp < num2._number[i]) || (temp == 0xFFFFFFFFFFFFFFFF && carry == 1) ? 1 : 0);
        num3._number[i] = temp + carry;

        return num3;
    }

    BigInt BigInt::operator-(const BigInt& num2) const {
        return *this + (-num2);
    }

    BigInt BigInt::operator*(BigInt num2) const {
        BigInt num3(0);
        uint64_t judgement;
        int i, j;

        for (i = 0; i < LONGLONG_NUM; i++) {

            judgement = 0x1;
            for (j = 0; j < 64; j++) {

                if ((_number[i] & judgement) != 0) {
                    num3 += num2;
                }

                num2 <<= 1;
                judgement <<= 1;
            }
        }

        num3._sign = _sign ^ num2._sign;

        return num3;
    }

    BigInt BigInt::operator/(BigInt num2) const {
        BigInt remainder, num1, quotient(0), temp(1);
        int temp_sign = _sign ^ num2._sign;

        if (num2 == 0) {
            throw "NaN";
        }

        if (_sign == 1) {
            num1 = -(*this);
        }
        else {
            num1 = *this;
        }

        if (num2._sign == 1) {
            num2 = -num2;
        }

        for (int i = 1; i <= LONGLONG_NUM * 64; i++) {
            remainder <<= 1;
            remainder |= ((num1 >> LONGLONG_NUM * 64 - i) & temp);

            quotient <<= 1;
            if (remainder >= num2) {
                remainder -= num2;
                quotient |= temp;
            }
        }

        if (temp_sign == 1){
            return -quotient;
        }

        return quotient;
    }

    BigInt BigInt::operator%(BigInt num2) const {
        BigInt remainder, num1, quotient(0), temp(1);

        if (num2 == 0) {
            throw "NaN";
        }

        if (_sign == 1) {
            num1 = -*this;
        }
        else {
            num1 = *this;
        }

        if (num2._sign == 1) {
            num2 = -num2;
        }

        for (int i = 1; i <= LONGLONG_NUM * 64; i++) {
            remainder <<= 1;
            remainder |= ((num1 >> LONGLONG_NUM * 64 - i) & temp);

            quotient <<= 1;
            if (remainder >= num2) {
                remainder -= num2;
                quotient |= temp;
            }
        }

        if (_sign == 1){
            return -remainder;
        }

        return remainder;
    }

    BigInt& BigInt::operator+=(const BigInt& num2) {
        int i, carry = 0, carry_next;
        uint64_t temp;

        for (i = 0; i < LONGLONG_NUM - 1; i++) {
            temp = _number[i] + num2._number[i];
            carry_next = (temp < _number[i] && temp < num2._number[i]) || (temp == 0xFFFFFFFFFFFFFFFF && carry == 1) ? 1 : 0;
            _number[i] = temp + carry;
            carry = carry_next;
        }
        temp = _number[i] + num2._number[i];
        _sign = (_sign ^ num2._sign) ^ ((temp < _number[i] && temp < num2._number[i]) || (temp == 0xFFFFFFFFFFFFFFFF && carry == 1) ? 1 : 0);
        _number[i] = temp + carry;

        return *this;
    }

    BigInt& BigInt::operator-=(const BigInt& num2) {
        return *this += (-num2);
    }

    BigInt& BigInt::operator*=(const BigInt& num2) {
        *this = *this * num2;
        return *this;
    }

    BigInt& BigInt::operator/=(const BigInt& num2) {
        *this = *this / num2;
        return *this;
    }

    BigInt& BigInt::operator%=(const BigInt& num2) {
        *this = *this % num2;
        return *this;
    }

    // 前置重载
    BigInt& BigInt::operator++() {
        int carry = _number[0] == 0xFFFFFFFFFFFFFFFF ? 1 : 0, carry_next;
        _number[0]++;
        for (int i = 1; i < LONGLONG_NUM; i++){
            carry_next = _number[i] == 0xFFFFFFFFFFFFFFFF && carry == 1 ? 1 : 0;
            _number[i] += carry;
            carry = carry_next;
        }

        if (carry == 1){
            _sign = _sign == 0 ? 1 : 0;
        }

        return *this;
    }

    // 后置重载
    BigInt BigInt::operator++(int) {
        BigInt num3(*this);
        ++(*this);

        return num3;
    }

    // 前置重载
    BigInt& BigInt::operator--() {
        BigInt temp(-1);
        *this += temp;

        return *this;
    }

    // 后置重载
    BigInt BigInt::operator--(int) {
        BigInt num3(*this);
        --(*this);

        return num3;
    }

    bool BigInt::operator==(const BigInt& num2) const {
        if (_sign != num2._sign){
            return false;
        }
        for (int i = 0; i < LONGLONG_NUM; i++){
            if (_number[i] != num2._number[i]){
                return false;
            }
        }
        return true;
    }

    bool BigInt::operator!=(const BigInt& num2) const {
        if (_sign != num2._sign){
            return true;
        }
        for (int i = 0; i < LONGLONG_NUM; i++){
            if (_number[i] != num2._number[i]){
                return true;
            }
        }
        return false;
    }

    bool BigInt::operator>(const BigInt& num2) const {
        if (_sign == 0 && num2._sign == 1){
            return true;
        }
        else if (_sign == 1 && num2._sign == 0){
            return false;
        }

        for (int i = LONGLONG_NUM - 1; i >= 0; i--){
            if (_number[i] > num2._number[i]){
                return true;
            }
            else if (_number[i] < num2._number[i]){
                return false;
            }
        }
        return false;
    }

    bool BigInt::operator<(const BigInt& num2) const {
        if (_sign == 0 && num2._sign == 1){
            return false;
        }
        else if (_sign == 1 && num2._sign == 0){
            return true;
        }

        for (int i = LONGLONG_NUM - 1; i >= 0; i--){
            if (_number[i] > num2._number[i]){
                return false;
            }
            else if (_number[i] < num2._number[i]){
                return true;
            }
        }
        return false;
    }

    bool BigInt::operator>=(const BigInt& num2) const {
        if (_sign == 0 && num2._sign == 1){
            return true;
        }
        else if (_sign == 1 && num2._sign == 0){
            return false;
        }

        for (int i = LONGLONG_NUM - 1; i >= 0; i--){
            if (_number[i] > num2._number[i]){
                return true;
            }
            else if (_number[i] < num2._number[i]){
                return false;
            }
        }
        return true;
    }

    bool BigInt::operator<=(const BigInt& num2) const {
        if (_sign == 0 && num2._sign == 1){
            return false;
        }
        else if (_sign == 1 && num2._sign == 0){
            return true;
        }

        for (int i = LONGLONG_NUM - 1; i >= 0; i--){
            if (_number[i] > num2._number[i]){
                return false;
            }
            else if (_number[i] < num2._number[i]){
                return true;
            }
        }
        return true;
    }

    BigInt BigInt::operator&(const BigInt& num2) const {
        BigInt num3;
        num3._sign = _sign & num2._sign;
        for (int i = 0; i < LONGLONG_NUM; i++){
            num3._number[i] = _number[i] & num2._number[i];
        }
        return num3;
    }

    BigInt BigInt::operator|(const BigInt& num2) const {
        BigInt num3;
        num3._sign = _sign | num2._sign;
        for (int i = 0; i < LONGLONG_NUM; i++){
            num3._number[i] = _number[i] | num2._number[i];
        }
        return num3;
    }

    BigInt BigInt::operator^(const BigInt& num2) const {
        BigInt num3;
        num3._sign = _sign ^ num2._sign;
        for (int i = 0; i < LONGLONG_NUM; i++){
            num3._number[i] = _number[i] ^ num2._number[i];
        }
        return num3;
    }

    BigInt BigInt::operator~() const {
        BigInt num3;
        num3._sign = _sign == 0 ? 1 : 0;
        for (int i = 0; i < LONGLONG_NUM; i++){
            num3._number[i] = ~_number[i];
        }
        return num3;
    }

    BigInt& BigInt::operator&=(const BigInt& num2) {
        _sign = _sign & num2._sign;
        for (int i = 0; i < LONGLONG_NUM; i++){
            _number[i] = _number[i] & num2._number[i];
        }
        return *this;
    }

    BigInt& BigInt::operator|=(const BigInt& num2) {
        _sign = _sign | num2._sign;
        for (int i = 0; i < LONGLONG_NUM; i++){
            _number[i] = _number[i] | num2._number[i];
        }
        return *this;

    }

    BigInt& BigInt::operator^=(const BigInt& num2) {
        _sign = _sign ^ num2._sign;
        for (int i = 0; i < LONGLONG_NUM; i++){
            _number[i] = _number[i] ^ num2._number[i];
        }
        return *this;
    }

    BigInt BigInt::operator<<(const unsigned int offset) const{
        BigInt num3;
        int i, j;
        num3._sign = _sign;

        if (offset == 0){
            return *this;
        }

        for (i = 0; i < offset / 64 && i < LONGLONG_NUM; i++){
            num3._number[i] = 0;
        }

        if (i == LONGLONG_NUM){
            return num3;
        }

        for (j = 0; i < LONGLONG_NUM - 1; i++, j++){
            num3._number[i + 1] = _number[j] >> (64 - offset % 64);
            num3._number[i] |= _number[j] << offset % 64;
        }
        num3._number[i] |= _number[j] << offset % 64;
        return num3;
    }

    BigInt BigInt::operator>>(const unsigned int offset) const{
        BigInt num3;
        int i, j;

        if (offset == 0){
            return *this;
        }

        num3._sign = _sign;

        for (i = LONGLONG_NUM - 1; i > LONGLONG_NUM - offset / 64 - 1 && i > 0; i--){
            num3._number[i] = 0;
        }

        if (i == 0){
            return num3;
        }

        for (j = LONGLONG_NUM - 1; i > 0 && j >= 0; i--, j--){
            num3._number[i - 1] = _number[j] << (64 - offset % 64);
            num3._number[i] |= _number[j] >> offset % 64;
        }
        num3._number[i] |= _number[j] >> offset % 64;

        return num3;
    }

    BigInt& BigInt::operator<<=(const unsigned int offset){
        *this = *this << offset;
        return *this;
    }

    BigInt& BigInt::operator>>=(const unsigned int offset){
        *this = *this >> offset;
        return *this;
    }

    BigInt::~BigInt() {}

    istream& operator>>(istream& in, BigInt& num) {
        char* str = new char[64 * num.LONGLONG_NUM + 2];
        int length;

        in >> str;
        str[64 * num.LONGLONG_NUM + 1] = '\0';
        length = strlen(str);

        if (strtobigint(str, length + 1, num) < 0){
            delete[] str;
            throw "Error in >>";
        }

        delete[] str;
        return in;
    }

    ostream& operator<<(ostream& out, const BigInt& num) {
        char* str = new char[64 * num.LONGLONG_NUM + 2];

        str[64 * num.LONGLONG_NUM + 1] = '\0';

        if (biginttostr(str, 64 * num.LONGLONG_NUM + 2, num) < 0){
            delete[] str;
            throw "";
        }

        out << str;

        delete[] str;
        return out;
    }

    int strtobigint(const char* str, const int size, BigInt& num) {
        if (str == NULL || size <= 0) {
            return 0;
        }

        BigInt base(1);
        int length = strnlen_s(str, size);

        num = 0;

        if (str[0] == '-') {
            for (int i = length - 1; i >= 1; i--, base *= 10) {
                if (str[i] < '0' || str[i] > '9') {
                    return -i;
                }
                num += base * (str[i] - '0');
            }
            num = -num;
        }
        else {
            for (int i = length - 1; i >= 0; i--, base *= 10) {
                if (str[i] < '0' || str[i] > '9') {
                    return -i;
                }
                num += base * (str[i] - '0');
            }
        }

        return length;
    }

    int biginttostr(char* str, const int size, BigInt num) {
        if (str == NULL || size <= 0) {
            return 0;
        }

        int length, start;
        BigInt remainder(0), quotient(0);

        if (num._sign == 1){
            num = -num;
            start = 1;
            str[0] = '-';
        }
        else{
            start = 0;
        }

        if (num == 0){
            str[0] = '0';
            str[1] = '\0';

            return 2;
        }

        for (length = start; num != 0 && length < size; length++) {
            // num / 10
            {
                BigInt temp(1);

                remainder = 0;
                quotient = 0;
                for (int i = 1; i <= num.LONGLONG_NUM * 64; i++) {
                    remainder <<= 1;
                    remainder |= ((num >> num.LONGLONG_NUM * 64 - i) & temp);

                    quotient <<= 1;
                    if (remainder >= 10) {
                        remainder -= 10;
                        quotient |= temp;
                    }
                }
            }
            str[length] = '0' + remainder._number[0];
            num = quotient;
        }

        for (int i = start, j = length - 1, temp; i < j; i++, j--) {
            temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
        str[length] = '\0';

        return length + 1;
    }
}